1. Technical Field
This invention relates to computer storage of information and, more particularly, to a method of assigning reclaim vectors in a partitioned cache with dynamic resource allocation.
2. Description of the Related Art
A computer system typically includes an information processor coupled to a hierarchical staged storage system. The type of storage employed in each staging location relative to the processor is normally determined by balancing requirements for speed, capacity, and cost. Computer processes continually refer to this storage over their executing lifetimes, both reading from and writing to the staged storage system. These references include self-referencing as well as references to every type of other process, overlay or data. It is well-known in the art that data storage devices using high-speed random access memory (RAM) can be referenced orders of magnitude faster than high volume direct-access storage devices (DASD's) using rotating magnetic media. Such electronic RAM storage typically relies upon high-speed transfer of electrical charges over short distances while DASD's typically operate mechanically by rotating a data storage position on a magnetic disk with respect to read-write heads. The relative cost per bit of storage for DASD and RAM makes it necessary to use DASD for bulk storage and electronic RAM for processor internal memory and caching.
In a multi-echelon staged memory system, a cache is typically placed between a processor and a larger but slower memory device. For instance, caches employing appropriate devices are found between a processor and main memory and between main memory and a DASD. The caching technique arose from the observation that processors frequently cluster their references in time and space to small sub-sets of all data stored. Thus, if 80% of the immediate references are to 5% of the data space, then storing that popular 5% in cache significantly decreases average reference time because of the substantial access speed advantage of cache over main storage. The fundamental caching problem involves establishing an efficient scheme for allocating cache spatial and temporal resources among multiple concurrent processes and their referenced data.
When data referenced by a process is found in the cache memory, it is a "hit" and a copy of the requested data is sent to the requesting process. When the desired data is not found, it is a "miss" and the requested data is read from the larger, slower main storage device and transferred both to cache and to the requesting process. When the "miss" data is added to cache, it replaces selected data already in cache. When the replaced data is selected according to the Least Recently Used (LRU) algorithm, the cache is referred to as an LRU cache.
A partitioned cache is one whose storage is divided into separate domains or partitions. Data with similar performance requirements are put into the same partition. The reason for this is to isolate the effects of managing high performance data from low performance data and vice versa. This allows a greater range of data to be effectively managed by a single cache. It may be implemented as a software cache in main memory or as a hardware cache, for example in the disk drive controller. A partitioned cache is of a fixed size, but the size of the partitions that make up the cache may vary through a process of dynamic reallocation of memory. These dynamic caches are controlled by a program operating on a processor or controller. Such caches employ some method of determining optimal partition sizes and shifting resources between the partitions to achieve the optimum size as it is updated. For example, this optimization may be based on the hit/miss ratio performance of each partition. Other partitioned caches statically allocate resources to each partition and avoid the problems inherent in dynamic reassignment of cache resources.
The cache resource used to store information from a single page is called a frame. When a frame is reallocated, the page of data it contains is dropped so that the frame can be utilized to store information for a different page associated with a different partition. This "stealing" of a frame typically occurs when a partition has a page cache miss reference. During a read or write operation to the cache, a miss occurs when data for the page being written does not already exist in the cache. Essentially, when a frame must be stolen to complete a cache access, a steal policy determines from which partition to steal the frame. The act of stealing a frame from one partition to be used in another, shifts cache resources among the partitions and accomplishes the dynamic reassignment to achieve the optimum size.
A method of establishing such a steal policy which minimizes the logic executed during a cache miss is to establish reclaim vectors for each partition. A reclaim vector for a partition is a list of numbers, wherein each number indicates how many frames should be stolen from a corresponding partition. As frames are stolen from other partitions, the reclaim vector is iteratively reduced to reflect the stolen pages.
Most methods of dynamically determining optimal sizes for partitions rely on periodically examining the performance of the cache and making adjustments. The period between the examinations is called a management interval. In a partitioned cache that dynamically assigns resources among the partitions through the use of a steal policy controlled by reclaim vectors, a new set of reclaim vectors is set for each management interval.
When a partition does not have a reclaim vector or it has stolen enough pages to reduce its reclaim vector to contain only zeros and then a miss is generated for it, a page is stolen from the same partition to satisfy the request. Such partitions do not grow but may shrink depending on the reclaim vectors in effect for the other partitions.
At some point, it may be desirable to allow a partition to shrink to the point where it is not using any pages. This allows the resources of the cache to be fully utilized. However, when a partition is empty, or full of changed pages, then a cache-full condition will result unless there is a non-zero reclaim vector in effect for the partition.
A little used cache partition will have a very low optimum size. Thus, it is likely for cache-full conditions to occur when little used cache partitions become active between management intervals. Since cache-full conditions are very disruptive to cache performance, it would be desirable to provide a method of avoiding the cache-full condition during the current management interval.